import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

import lombok.extern.slf4j.Slf4j;

/**
 * 图
 */
@Slf4j
public class DataStructure_5_graph {
	/**
	 * 邻接矩阵(对于稀疏图而言，定点多，边少，浪费了空间)
	 * O(n+n^2+e)
	 * @author zlzhangn
	 */
	static class AM_graph{
		int numVertexes;	//顶点数
		int numEdges;	//边数
		int[][] edgeArr;	//邻接矩阵（边表）
		final int INFINITY = Integer.MAX_VALUE;
		void create_graph(){
			Scanner scanner = new Scanner(System.in);
			System.out.println("请输入顶点数！");
			numVertexes = scanner.nextInt();
			System.out.println("请输入边数！");
			numEdges = scanner.nextInt();
			edgeArr = new int[numVertexes][numVertexes];
			for(int i=0;i<numVertexes; i++)
				for(int j=0;j<numVertexes;j++)
					edgeArr[i][j]=INFINITY;
			System.out.println("请输入顶点a和顶点b的下标，以及权重m. a,b,m;a,b,m");
			String inStr = scanner.next();
			String[] strArr = inStr.split(";");
			for(int i=0; i < strArr.length; i++){
				String[] strArr2 = strArr[i].split(",");
				int a = Integer.valueOf(strArr2[0]);
				int b = Integer.valueOf(strArr2[1]);
				int m = Integer.valueOf(strArr2[2]);
				edgeArr[a][b] = m;
				edgeArr[b][a] = m;
			}
			scanner.close();
		}
	}
	
	/**
	 * 邻接表
	 * O(n+e)
	 */
	static class AL_graph{
		int numVertexes;
		VertexNode[] vertexArr;
		int numEdges;
		class EdgeNode{
			int index;
			int weight;
			EdgeNode next;
			EdgeNode(){}
			EdgeNode(int index,int weight){
				this.index = index;
				this.weight = weight;
			}
		}
		class VertexNode{
			String data;
			EdgeNode next;
			VertexNode(String data){this.data=data;}
		}
		void create_graph(){
			Scanner scanner = new Scanner(System.in);
			System.out.println("请输入顶点数！");
			numVertexes = scanner.nextInt();
			vertexArr = new VertexNode[numVertexes];
			for(int i=0; i<numVertexes; i++){
				vertexArr[i] = new VertexNode(String.valueOf(i));
			}
			System.out.println("请输入边数！");
			numEdges = scanner.nextInt();
			System.out.println("请输入顶点a和顶点b的下标，以及权重m(a,b,m;a,b,m)");
			String inStr = scanner.next();
			String[] strArr = inStr.split(";");
			for(int i=0; i<strArr.length; i++){
				String[] strArr2 = strArr[i].split(",");
				VertexNode a = vertexArr[Integer.valueOf(strArr2[0])];
				VertexNode b = vertexArr[Integer.valueOf(strArr2[1])];
				int weight = Integer.valueOf(strArr2[2]);
				EdgeNode nodeA = new EdgeNode(Integer.valueOf(strArr2[0]), weight);
				EdgeNode nodeB = new EdgeNode(Integer.valueOf(strArr2[1]), weight);
				if(a.next==null){
					a.next = nodeB;
				}else{
					nodeB.next=a.next;
					a.next=nodeB;
				}
				if(b.next==null){
					b.next = nodeA;
				}else{
					nodeA.next=b.next;
					b.next=nodeA;
				}
			}
			for(int i=0; i<numVertexes; i++){
				System.out.println(i+": ");
				EdgeNode node = vertexArr[i].next;
				while(node!=null){
					System.out.print(node.index+",");
					node = node.next;
				}
				System.out.println();
			}
			scanner.close();
		}
	}
	
	/**
	 * 图的边集数组存储方式 （关注重点在边）
	 */
	static class EdgeSet_graph{
		int[] vertex;
		EdgeNode[] edgeSet;
		class EdgeNode implements Comparable<EdgeNode>{
			int start;
			int end;
			int weight;
			public int compareTo(EdgeNode o) {
				return this.weight-o.weight;
			}
			EdgeNode(int start, int end, int weight){
				this.start = start;
				this.end = end;
				this.weight = weight;
			}
		}
		void create(){
			Scanner scanner = new Scanner(System.in);
			System.out.println("请输入顶点数！");
			int numVertex = scanner.nextInt();
			vertex = new int[numVertex];
			System.out.println("请输入边数！");
			int numEdge = scanner.nextInt();
			edgeSet = new EdgeNode[numEdge];
			System.out.println("请输入ijm;！");
			String ijm = scanner.next();
			String[] strArr = ijm.split(";");
			for(int i=0; i<strArr.length; i++){
				String[] strArr2 = strArr[i].split(",");
				int start = Integer.parseInt(strArr2[0]);
				int end = Integer.parseInt(strArr2[1]);
				int weight = Integer.parseInt(strArr2[2]);
				EdgeNode edge = new EdgeNode(start, end, weight);
				edgeSet[i] = edge;
			}
			scanner.close();
		}
	}
	
	/**
	 * 深度优先搜索（Depth-First-Search ）
	 */
	public static class Graph_df_search{
		private boolean[] visited;
		private void dfs(AM_graph graph,int i){
			visited[i] = true;
			log.debug("已找到{}",i);
			for(int j=0; j<graph.numVertexes; j++){
				if(graph.edgeArr[i][j]!=graph.INFINITY && !visited[j]){
					dfs(graph, j);
				}
			}
		}
		//O(n^2)
		public void dfSearch(AM_graph graph){
			visited = new boolean[graph.numVertexes];
			for(int i=0; i<graph.numVertexes; i++){
				if(!visited[i]){
					dfs(graph,i);
				}
			}
		}
		private void dfs2(AL_graph graph,int i){
			visited[i] = true;
			log.debug("已找到{}",i);
			AL_graph.EdgeNode node = graph.vertexArr[i].next;
			while(node!=null && !visited[node.index]){
				dfs2(graph,node.index);
				node=node.next;
			}
		}
		//O(n+e)
		public void dfSearch2(AL_graph graph){
			visited = new boolean[graph.numVertexes];
			for(int i=0; i<graph.numVertexes; i++){
				if(!visited[i]){
					dfs2(graph,i);
				}
			}
		}
	}
	
	/**
	 * 广度优先搜索（Breadth-First-Search）
	 * @author zlzhangn
	 */
	public static class Graph_bf_search{
		public void bfSearch(AM_graph graph){
			boolean[] visited = new boolean[graph.numVertexes];
			Queue<Integer> queue = new LinkedList<Integer>();
			for(int i=0; i<graph.numVertexes; i++){
				if(!visited[i]){
					visited[i] = true;
					System.out.println("已找到："+i);
					queue.add(i);
					while(queue.peek()!=null){
						int j = queue.poll();
						for(int k=0; k<graph.numVertexes; k++){
							if(graph.edgeArr[j][k]!=graph.INFINITY && !visited[k]){
								visited[k] = true;
								System.out.print("已找到："+k);
								queue.add(k);
							}
						}
					}
				}
			}
		}
		public void bfSearch2(AL_graph graph){
			boolean[] visited = new boolean[graph.numVertexes];
			Queue<Integer> queue = new LinkedList<Integer>();
			for(int i=0; i<graph.numVertexes; i++){
				if(!visited[i]){
					visited[i] = true;
					System.out.println("已找到："+i);
					queue.add(i);
					while(queue.peek()!=null){
						int j = queue.poll();
						AL_graph.EdgeNode node = graph.vertexArr[j].next;
						while(node!=null){
							if(!visited[node.index]){
								visited[node.index] = true;
								System.out.print("已找到："+node.index);
								queue.add(node.index);
							}
							node=node.next;
						}
					}
				}
			}
		}
	}
	
	/**
	 * 最小生成树（普里姆算法prim）
	 * O(n^2)
	 */
	public static void MiniSpanTree_prim(AM_graph graph){
		int k=0;
		//保存相关顶点下标
		int[] vertexArr = new int[graph.numVertexes];
		//保存相关顶点间边的权值
		int[] lowCost = new int[graph.numVertexes];
		/*初始化第一个权值为零，即V0已加入生成树*/
		lowCost[0] = 0;
		//初始化第一个顶点下标为0
		vertexArr[0] = 0;
		//循环除下标0以外的全部顶点
		for(int i=1; i<graph.numVertexes; i++){
			//将V0顶点与之有边的权值存入数组
			lowCost[i] = graph.edgeArr[0][i];
			//初始化都为V0的下标
			vertexArr[i] = 0;
		}
		log.debug("lowCost-{}",Arrays.toString(lowCost));
		log.debug("vertexArr-{}",Arrays.toString(vertexArr));
		for(int i=1; i<graph.numVertexes; i++){
			//初始化最小权值 
			int min = graph.INFINITY;
			int j=1;k =0;
			//循环全部顶点
			while(j<graph.numVertexes){
				//如果权值不等于0，且权值小于min
				if(lowCost[j]!=0 && lowCost[j]<min){
					min = lowCost[j];	//让权值成为最小值
					k = j;				//将当前最小值的下标存入k
				}
				j++;
			}
			//打印当前顶点边中权值最小的边
			log.debug("min:{};最小权值边{}-{}",min,vertexArr[k],k);
			//将当前顶点的权值设为0，表示此顶点已经完成任务
			lowCost[k] = 0;
			//循环所有顶点
			for(j=1; j<graph.numVertexes; j++){
				//若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值
				if(lowCost[j]!=0 && graph.edgeArr[k][j]<lowCost[j]){
					//将较小值存入lowCost
					lowCost[j] = graph.edgeArr[k][j];
					vertexArr[j] = k;
				}
			}
			log.debug("lowCost-{}",Arrays.toString(lowCost));
			log.debug("vertexArr-{}",Arrays.toString(vertexArr));
		}
	}
	
	/**
	 * 堆（基于完全二叉树实现，新增，删除都是O(logn)）
	 * @author zlzhangn
	 *
	 */
	public static class MinHeap<AnyType extends Comparable<? super AnyType>>{
		private AnyType[] element;	//堆中元素
		private int size;		//堆中元素个数
		private int capacity;	//堆最大容量
		public  MinHeap(int capacity){
			this.element = (AnyType[])new Comparable[capacity+1];
			this.capacity = capacity;
			this.size = 0;
			//哨兵元素，控制循环结束
			this.element[0] = null;
		} 
		boolean isFull(){
			return size == capacity;
		}
		boolean isEmpty(){
			return size == 0;
		}
		void insert(AnyType node){
			if(isFull()){
				log.info("堆已满！！");
				return;
			}
			int i = ++size;
			for(;element[i/2]!=null && element[i/2].compareTo(node)>0;i/=2){
				element[i] = element[i/2];	//上滤比交换元素块
			}
			element[i] = node;
		}
		AnyType deleteMin(){
			AnyType e = element[1];
			element[1] = element[size--];
			percolateDown(1);
			return e;
		}
		void percolateDown(int hole){
			int child;
	        AnyType tmp = element[ hole ];

	        for( ; hole * 2 <= size; hole = child )
	        {
	            child = hole * 2;
	            if( child != size &&
	            		element[ child + 1 ].compareTo( element[ child ] ) < 0 )
	                child++;
	            if( element[ child ].compareTo( tmp ) < 0 )
	            	element[ hole ] = element[ child ];
	            else
	                break;
	        }
	        element[ hole ] = tmp;
		}
		
	}
	
	/**
	 * 克鲁斯卡尔算法(kruskal)
	 * O(eloge)
	 */
	public static void Kruskal(EdgeSet_graph graph){
		//根据邻接矩阵生成最小堆（最小堆 ：插入O（logn），删除O（logn），找最小值O（1））
		MinHeap<EdgeSet_graph.EdgeNode> minHeap = new MinHeap<>(graph.edgeSet.length);
		for(int i=0; i<graph.edgeSet.length; i++){
			minHeap.insert(graph.edgeSet[i]);
		}
		int minTree[] = new int[graph.vertex.length];
		//从最小权重边开始循环
		while(!minHeap.isEmpty()){
			EdgeSet_graph.EdgeNode edge = minHeap.deleteMin();
			//利用并查集，判断是否存在环路
			int start = find(minTree,edge.start);
			int end = find(minTree,edge.end);
			//如果两个顶点不在一个集合中，则添加到最小生成树
			//log.info("start:{} end:{} weight:{}",edge.start,edge.end,edge.weight);
			if(start!=end){
				System.out.println(start+" "+end);
				minTree[start]=end;
			}
		}
	}
	
	public static int find(int[] parents, int target){
		while(parents[target]>0){
			target = parents[target];
		}
		return target;
	}
	
	/**
	 * 迪杰斯特拉算法（Di-jkstra），求最短路径
	 */
	public static void Di_jkstra(AL_graph graph){
		int maxVertex;
		int pathArr[];	//用来存储最短路径下标的数组
		int shortPathArr[]; //存放各顶点最短路径权值和
		
	}
	
	public static void main(String[] args) throws Exception{
		/*AL_graph graph = new AL_graph();
		graph.create_graph();
		Graph_bf_search search = new Graph_bf_search();
		search.bfSearch2(graph);*/
		//AM_graph graph = new AM_graph();
		//graph.create_graph();
		//MiniSpanTree_prim(graph);
		EdgeSet_graph graph = new EdgeSet_graph();
		graph.create();
		Kruskal(graph);
	}
	
	
}
